home *** CD-ROM | disk | FTP | other *** search
/ Atari Mega Archive 1 / Atari Mega Archive - Volume 1.iso / lists / mint / l_1199 / 1090 < prev    next >
Encoding:
Internet Message Format  |  1994-08-27  |  3.4 KB
  1. Subject: Re: tosfs, faster hash function...
  2. Date: Wed, 23 Feb 94 23:16:44 CET
  3. From: Juergen Lock <nox@jelal.north.de>
  4. In-Reply-To: <9402221314.AA11542@math.uni-muenster.de>; from "Julian Reschke" at Feb 22, 94 2:14 pm
  5. Message-Id: <9402232216.AA00510@jelal.north.de>
  6.  
  7. Julian Reschke writes:
  8.  
  9. > Re inodes: everybofy with large TOS filesystems should verify that
  10. > the (computed) inodes indeed are unique (as I said: it's highly
  11. > probale, but it can't be guaranteed). If you have gnu-find or my
  12. > find.ttp (mupftl02.tos, ftp.uni-muenster.de, pub/atari/Gemini),
  13. > you can try the following script:
  14. > 
  15. > find \ -printf "%i\n" > inodes.all
  16. > sort inodes.all > inodes.tot
  17. > uniq inodes.tot > inodes.uni
  18. > wc -l inodes.tot inodes.uni
  19.  
  20.  or diff -u ...
  21.  
  22. > rm inodes.tot inodes.uni inodes.all
  23. > 
  24.  ..but thats not why i followup :)
  25.  
  26. >+ 
  27. >+ #define UPDC32(octet, crc) (((crc) << 8) ^ crctab[((crc) >> 24) ^ (octet)])
  28.  
  29.  hmm shifts are slow on 68000...  here is one that should be a bit faster,
  30. from dbz (cnews):
  31.  
  32. /*
  33.  * This is a simplified version of the pathalias hashing function.
  34.  * Thanks to Steve Belovin and Peter Honeyman
  35.  *
  36.  * hash a string into a long int.  31 bit crc (from andrew appel).
  37.  * the crc table is computed at run time by crcinit() -- we could
  38.  * precompute, but it takes 1 clock tick on a 750.
  39.  *
  40.  * This fast table calculation works only if POLY is a prime polynomial
  41.  * in the field of integers modulo 2.  Since the coefficients of a
  42.  * 32-bit polynomial won't fit in a 32-bit word, the high-order bit is
  43.  * implicit.  IT MUST ALSO BE THE CASE that the coefficients of orders
  44.  * 31 down to 25 are zero.  Happily, we have candidates, from
  45.  * E. J.  Watson, "Primitive Polynomials (Mod 2)", Math. Comp. 16 (1962):
  46.  *    x^32 + x^7 + x^5 + x^3 + x^2 + x^1 + x^0
  47.  *    x^31 + x^3 + x^0
  48.  *
  49.  * We reverse the bits to get:
  50.  *    111101010000000000000000000000001 but drop the last 1
  51.  *         f   5   0   0   0   0   0   0
  52.  *    010010000000000000000000000000001 ditto, for 31-bit crc
  53.  *       4   8   0   0   0   0   0   0
  54.  */
  55.  
  56. #define POLY 0x48000000L    /* 31-bit polynomial (avoids sign problems) */
  57.  
  58. static long CrcTable[128];
  59.  
  60. /*
  61.  - crcinit - initialize tables for hash function
  62.  */
  63. static void
  64. crcinit()
  65. {
  66.     register int i, j;
  67.     register long sum;
  68.  
  69.     for (i = 0; i < 128; ++i) {
  70.         sum = 0L;
  71.         for (j = 7 - 1; j >= 0; --j)
  72.             if (i & (1 << j))
  73.                 sum ^= POLY >> j;
  74.         CrcTable[i] = sum;
  75.     }
  76.     DEBUG(("crcinit: done\n"));
  77. }
  78.  
  79. /*
  80.  - hash - Honeyman's nice hashing function
  81.  */
  82. static long
  83. hash(name, size)
  84. register char *name;
  85. register int size;
  86. {
  87.     register long sum = 0L;
  88.  
  89.     while (size--) {
  90.         sum = (sum >> 7) ^ CrcTable[(sum ^ (*name++)) & 0x7f];
  91.     }
  92.     DEBUG(("hash: returns (%ld)\n", sum));
  93.     return(sum);
  94. }
  95.  
  96.  i have not done tests which one is better for filenames but there should
  97. be no difference.
  98.  
  99. >+ 
  100. >+ static unsigned long
  101. >+ filename_crc (const char *filename)
  102. >+ {
  103. >+     unsigned long s = 0;
  104. >+     unsigned int n = 0;
  105. >+     
  106. >+     /* skip x: */
  107. >+     filename += 2;
  108. >+     
  109. >+     while (*filename) {
  110. >+         s = UPDC32 (*filename++, s);
  111. >+         n++;
  112. >+     }
  113. >+ 
  114. >+     while (n != 0) {
  115. >+         s = UPDC32 (n & 0377, s);
  116. >+         n >>= 8;
  117. >+     }
  118. >+     
  119. >+     return s;
  120. >+ }
  121. >+ 
  122. >+ #endif
  123.  
  124.  does the second loop improve results?
  125.  
  126.  just a thought...
  127.     Juergen
  128.  
  129. PS: there is a problem too with using start clusters: 0 byte files...
  130. -- 
  131. J"urgen Lock / nox@jelal.north.de / UUCP: ..!uunet!unido!uniol!jelal!nox
  132.                                 ...ohne Gewehr
  133. PGP public key fingerprint =  8A 18 58 54 03 7B FC 12  1F 8B 63 C7 19 27 CF DA 
  134.